// 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

// 说明：

// 拆分时可以重复使用字典中的单词。
// 你可以假设字典中没有重复的单词。
// 示例 1：

// 输入: s = "leetcode", wordDict = ["leet", "code"]
// 输出: true
// 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
// 示例 2：

// 输入: s = "applepenapple", wordDict = ["apple", "pen"]
// 输出: true
// 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
//      注意你可以重复使用字典中的单词。
// 示例 3：

// 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
// 输出: false

#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

// 记忆化数组
class Solution1 {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<int> memory(s.size(), -1); // 记忆化数组
        return check(s, wordSet, 0, memory);
    }
    bool check(string s, unordered_set<string>& wordSet, int start, vector<int>& memory) {
        if (start >= s.size()) return true;
        if (memory[start] != -1) return memory[start];
        for (int i = start + 1; i <= s.size(); ++i) {
            if (wordSet.count(s.substr(start, i - start)) && check(s, wordSet, i, memory)) {
                return memory[start] = 1; // 可以拆分，赋值为1
            }
        }
        return memory[start] = 0; // 不可以拆分，赋值为0
    }
};

// 动态规划
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> dp(n+1);
        dp[0] = true;
        for (int i{0}; i < n+1; ++i) {
            for (int j{0}; j < i; ++j) {
                if (dp[j] && wordSet.count(s.substr(j, i-j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string> wordDictSet{};
        for (auto& word : wordDict) {
            wordDictSet.insert(word);
        }
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i{1}; i <= n; ++i) {
            for (int j{0}; j < i; ++j) {
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                    dp[i] = true;
                    break; // 跳出内层for循环
                }
            }
        }
        return dp[n];
    }
};